//===--- OptRemarkGenerator.cpp -------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// In this pass, we define the opt-remark-generator, a simple SILVisitor that
/// attempts to infer opt-remarks for the user using heuristics.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "sil-opt-remark-gen"

#include "swift/Basic/Defer.h"
#include "swift/AST/SemanticAttrs.h"
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/OptimizationRemark.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILModule.h"
#include "swift/SIL/SILVisitor.h"
#include "swift/SILOptimizer/Analysis/RCIdentityAnalysis.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/raw_ostream.h"

using namespace swift;

static llvm::cl::opt<bool> ForceVisitImplicitAutogeneratedFunctions(
    "optremarkgen-visit-implicit-autogen-funcs", llvm::cl::Hidden,
    llvm::cl::desc(
        "Emit opt remarks even on implicit and autogenerated functions"),
    llvm::cl::init(false));

static llvm::cl::opt<bool> DecllessDebugValueUseSILDebugInfo(
    "optremarkgen-declless-debugvalue-use-sildebugvar-info", llvm::cl::Hidden,
    llvm::cl::desc(
        "If a debug_value does not have a decl, infer a value with a name from "
        "that info that has a loc set to the loc of the debug_value "
        "instruction itself. This is for testing purposes so it is easier to "
        "write SIL test cases for this pass"),
    llvm::cl::init(false));

//===----------------------------------------------------------------------===//
//                           Value To Decl Inferrer
//===----------------------------------------------------------------------===//

namespace {

struct ValueToDeclInferrer {
  using Argument = OptRemark::Argument;
  using ArgumentKeyKind = OptRemark::ArgumentKeyKind;

  RCIdentityFunctionInfo &rcfi;
  SmallVector<std::pair<SILType, Projection>, 32> accessPath;
  SmallVector<Operand *, 32> rcIdenticalSecondaryUseSearch;

  ValueToDeclInferrer(RCIdentityFunctionInfo &rcfi) : rcfi(rcfi) {}

  /// Given a value, attempt to infer a conservative list of decls that the
  /// passed in value could be referring to. This is done just using heuristics
  bool infer(ArgumentKeyKind keyKind, SILValue value,
             SmallVectorImpl<Argument> &resultingInferredDecls);

  /// Print out a note to \p stream that beings at decl and then if
  /// useProjectionPath is set to true iterates the accessPath we computed for
  /// decl producing a segmented access path, e.x.: "of 'x.lhs.ivar'".
  ///
  /// The reason why one may not want to emit a projection path note here is if
  /// one found an debug_value on a value that is rc-identical to the actual
  /// value associated with the current projection path. Consider the following
  /// SIL:
  ///
  ///    struct KlassPair {
  ///      var lhs: Klass
  ///      var rhs: Klass
  ///    }
  ///
  ///    struct StateWithOwningPointer {
  ///      var state: TrivialState
  ///      var owningPtr: Klass
  ///    }
  ///
  ///    sil @theFunction : $@convention(thin) () -> () {
  ///    bb0:
  ///      %0 = apply %getKlassPair() : $@convention(thin) () -> @owned KlassPair
  ///      // This debug_value's name can be combined...
  ///      debug_value %0 : $KlassPair, name "myPair"
  ///      // ... with the access path from the struct_extract here...
  ///      %1 = struct_extract %0 : $KlassPair, #KlassPair.lhs
  ///      // ... to emit a nice diagnostic that 'myPair.lhs' is being retained.
  ///      strong_retain %1 : $Klass
  ///
  ///      // In contrast in this case, we rely on looking through rc-identity
  ///      // uses to find the debug_value. In this case, the source info
  ///      // associated with the debug_value (%2) is no longer associated with
  ///      // the underlying access path we have been tracking upwards (%1 is in
  ///      // our access path list). Instead, we know that the debug_value is
  ///      // rc-identical to whatever value we were originally tracking up (%1)
  ///      // and thus the correct identifier to use is the direct name of the
  ///      // identifier alone since that source identifier must be some value
  ///      // in the source that by itself is rc-identical to whatever is being
  ///      // manipulated.
  ///      //
  ///      // The reason why we must do this is due to the behavior of the late
  ///      // optimizer and how it forms these patterns in the code.
  ///      %0a = apply %getStateWithOwningPointer() : $@convention(thin) () -> @owned StateWithOwningPointer
  ///      %1 = struct_extract %0a : $StateWithOwningPointer, #StateWithOwningPointer.owningPtr
  ///      strong_retain %1 : $Klass
  ///      %2 = struct $Array(%0 : $Builtin.NativeObject, ...)
  ///      debug_value %2 : $Array, ...
  ///    }
  void printNote(llvm::raw_string_ostream &stream, StringRef name,
                 bool shouldPrintAccessPath = true);

  /// Convenience overload that calls:
  ///
  ///   printNote(stream, decl->getBaseName().userFacingName(), shouldPrintAccessPath).
  void printNote(llvm::raw_string_ostream &stream, const ValueDecl *decl,
                 bool shouldPrintAccessPath = true) {
    printNote(stream, decl->getBaseName().userFacingName(),
              shouldPrintAccessPath);
  }

  /// Print out non-destructively the current access path we have found to
  /// stream.
  void printAccessPath(llvm::raw_string_ostream &stream);
};

} // anonymous namespace

void ValueToDeclInferrer::printAccessPath(llvm::raw_string_ostream &stream) {
  for (auto &pair : accessPath) {
    auto baseType = pair.first;
    auto &proj = pair.second;
    stream << ".";

    // WARNING: This must be kept insync with isSupportedProjection!
    switch (proj.getKind()) {
    case ProjectionKind::Upcast:
      stream << "upcast<" << proj.getCastType(baseType) << ">";
      continue;
    case ProjectionKind::RefCast:
      stream << "refcast<" << proj.getCastType(baseType) << ">";
      continue;
    case ProjectionKind::BitwiseCast:
      stream << "bitwise_cast<" << proj.getCastType(baseType) << ">";
      continue;
    case ProjectionKind::Struct:
      stream << proj.getVarDecl(baseType)->getBaseName();
      continue;
    case ProjectionKind::Tuple:
      stream << proj.getIndex();
      continue;
    case ProjectionKind::Enum:
      stream << proj.getEnumElementDecl(baseType)->getBaseName();
      continue;
    // Object -> Address projections can never be looked through.
    case ProjectionKind::Class:
    case ProjectionKind::Box:
    case ProjectionKind::Index:
    case ProjectionKind::TailElems:
      llvm_unreachable(
          "Object -> Address projection should never be looked through!");
    }

    llvm_unreachable("Covered switch is not covered?!");
  }
}

void ValueToDeclInferrer::printNote(llvm::raw_string_ostream &stream,
                                    StringRef name,
                                    bool shouldPrintAccessPath) {
  stream << "of '" << name;
  if (shouldPrintAccessPath)
    printAccessPath(stream);
  stream << "'";
}

// WARNING: This must be kept insync with ValueToDeclInferrer::printNote(...).
static SingleValueInstruction *isSupportedProjection(Projection p, SILValue v) {
  switch (p.getKind()) {
  case ProjectionKind::Upcast:
  case ProjectionKind::RefCast:
  case ProjectionKind::BitwiseCast:
  case ProjectionKind::Struct:
  case ProjectionKind::Tuple:
  case ProjectionKind::Enum:
    return cast<SingleValueInstruction>(v);
    // Object -> Address projections can never be looked through.
  case ProjectionKind::Class:
  case ProjectionKind::Box:
  case ProjectionKind::Index:
  case ProjectionKind::TailElems:
    return nullptr;
  }
  llvm_unreachable("Covered switch is not covered?!");
}

static bool hasNonInlinedDebugScope(SILInstruction *i) {
  if (auto *scope = i->getDebugScope())
    return !scope->InlinedCallSite;
  return false;
}

bool ValueToDeclInferrer::infer(
    ArgumentKeyKind keyKind, SILValue value,
    SmallVectorImpl<Argument> &resultingInferredDecls) {
  // Clear the stored access path at end of scope.
  SWIFT_DEFER {
    accessPath.clear();
  };
  SmallPtrSet<SILInstruction *, 8> visitedDebugValueInsts;

  // This is a linear IR traversal using a 'falling while loop'. That means
  // every time through the loop we are trying to handle a case before we hit
  // the bottom of the while loop where we always return true (since we did not
  // hit a could not compute case). Reassign value and continue to go to the
  // next step.
  while (true) {
    // First check for "identified values" like arguments and global_addr.
    if (auto *arg = dyn_cast<SILArgument>(value))
      if (auto *decl = arg->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, decl);
        }
        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), decl));
        return true;
      }

    if (auto *ga = dyn_cast<GlobalAddrInst>(value))
      if (auto *decl = ga->getReferencedGlobal()->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, decl);
        }
        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), decl));
        return true;
      }

    if (auto *ari = dyn_cast<AllocRefInst>(value)) {
      if (auto *decl = ari->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, decl);
        }
        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), decl));
        return true;
      }
    }

    if (auto *abi = dyn_cast<AllocBoxInst>(value)) {
      if (auto *decl = abi->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, decl);
        }

        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), decl));
        return true;
      }
    }

    if (auto *asi = dyn_cast<AllocStackInst>(value)) {
      if (auto *decl = asi->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          printNote(stream, decl);
        }
        resultingInferredDecls.push_back(
            Argument({keyKind, "InferredValue"}, std::move(msg), decl));
        return true;
      }
    }

    // Then visit our users (ignoring rc identical transformations) and see if
    // we can find a debug_value that provides us with a decl we can use to
    // construct an argument.
    //
    // The reason why we do this is that sometimes we reform a struct from its
    // constituant parts and then construct the debug_value from that. For
    // instance, if we FSOed.
    bool foundDeclFromUse = false;
    rcfi.visitRCUses(value, [&](Operand *use) {
      // Skip type dependent uses.
      if (use->isTypeDependent())
        return;

      // Then see if we have a debug_value that is associated with a non-inlined
      // debug scope. Such an instruction is an instruction that is from the
      // current function.
      auto *dvi = dyn_cast<DebugValueInst>(use->getUser());
      if (!dvi || !hasNonInlinedDebugScope(dvi))
        return;

      // See if we have already inferred this debug_value as a potential source
      // for this instruction. In such a case, just return.
      if (!visitedDebugValueInsts.insert(dvi).second)
        return;

      if (auto *decl = dvi->getDecl()) {
        std::string msg;
        {
          llvm::raw_string_ostream stream(msg);
          // If we are not a top level use, we must be a rc-identical transitive
          // use. In such a case, we just print out the rc identical value
          // without a projection path. This is because we now have a better
          // name and the name is rc-identical to whatever was at the end of the
          // projection path but is not at the end of that projection path.
          printNote(stream, decl,
                    use->get() == value /*print projection path*/);
        }
        resultingInferredDecls.emplace_back(
            OptRemark::ArgumentKey{keyKind, "InferredValue"}, std::move(msg),
            decl);
        foundDeclFromUse = true;
        return;
      }

      // If we did not have a decl, see if we were asked for testing
      // purposes to use SILDebugInfo to create a placeholder inferred
      // value.
      if (!DecllessDebugValueUseSILDebugInfo)
        return;

      auto varInfo = dvi->getVarInfo();
      if (!varInfo)
        return;

      auto name = varInfo->Name;
      if (name.empty())
        return;

      std::string msg;
      {
        llvm::raw_string_ostream stream(msg);
        printNote(stream, name, use->get() == value /*print projection path*/);
      }
      resultingInferredDecls.push_back(
          Argument({keyKind, "InferredValue"}, std::move(msg), dvi->getLoc()));
      foundDeclFromUse = true;
    });

    // At this point, we could not infer any argument. See if we can look up the
    // def-use graph and come up with a good location after looking through
    // loads and projections.
    if (auto *li = dyn_cast<LoadInst>(value)) {
      value = stripAccessMarkers(li->getOperand());
      continue;
    }

    if (auto proj = Projection(value)) {
      if (auto *projInst = isSupportedProjection(proj, value)) {
        value = projInst->getOperand(0);
        accessPath.emplace_back(value->getType(), proj);
        continue;
      }
    }

    // TODO: We could emit at this point a msg for temporary allocations.

    // If we reached this point, we finished falling through the loop and return
    // if we found any decls from uses. We always process everything so we /can/
    // potentially emit multiple diagnostics.
    return foundDeclFromUse;
  }
}

//===----------------------------------------------------------------------===//
//                        Opt Remark Generator Visitor
//===----------------------------------------------------------------------===//

namespace {

struct OptRemarkGeneratorInstructionVisitor
    : public SILInstructionVisitor<OptRemarkGeneratorInstructionVisitor> {
  SILModule &mod;
  OptRemark::Emitter ORE;

  /// A class that we use to infer the decl that is associated with a
  /// miscellaneous SIL value. This is just a heuristic that is to taste.
  ValueToDeclInferrer valueToDeclInferrer;

  OptRemarkGeneratorInstructionVisitor(SILFunction &fn,
                                       RCIdentityFunctionInfo &rcfi)
      : mod(fn.getModule()), ORE(DEBUG_TYPE, fn), valueToDeclInferrer(rcfi) {}

  void visitStrongRetainInst(StrongRetainInst *sri);
  void visitStrongReleaseInst(StrongReleaseInst *sri);
  void visitRetainValueInst(RetainValueInst *rvi);
  void visitReleaseValueInst(ReleaseValueInst *rvi);
  void visitAllocRefInst(AllocRefInst *ari);
  void visitAllocBoxInst(AllocBoxInst *abi);
  void visitSILInstruction(SILInstruction *) {}
};

} // anonymous namespace

void OptRemarkGeneratorInstructionVisitor::visitStrongRetainInst(
    StrongRetainInst *sri) {
  ORE.emit([&]() {
    using namespace OptRemark;
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                               sri->getOperand(), inferredArgs);
    (void)foundArgs;

    // Retains begin a lifetime scope so we infer scan forward.
    auto remark =
        RemarkMissed("memory", *sri,
                     SourceLocInferenceBehavior::ForwardScanAlwaysInfer)
        << "retain of type '" << NV("ValueType", sri->getOperand()->getType())
        << "'";
    for (auto arg : inferredArgs) {
      remark << arg;
    }
    return remark;
  });
}

void OptRemarkGeneratorInstructionVisitor::visitStrongReleaseInst(
    StrongReleaseInst *sri) {
  ORE.emit([&]() {
    using namespace OptRemark;
    // Releases end a lifetime scope so we infer scan backward.
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                               sri->getOperand(), inferredArgs);
    (void)foundArgs;

    auto remark =
        RemarkMissed("memory", *sri,
                     SourceLocInferenceBehavior::BackwardScanAlwaysInfer)
        << "release of type '" << NV("ValueType", sri->getOperand()->getType())
        << "'";
    for (auto arg : inferredArgs) {
      remark << arg;
    }
    return remark;
  });
}

void OptRemarkGeneratorInstructionVisitor::visitRetainValueInst(
    RetainValueInst *rvi) {
  ORE.emit([&]() {
    using namespace OptRemark;
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                               rvi->getOperand(), inferredArgs);
    (void)foundArgs;
    // Retains begin a lifetime scope, so we infer scan forwards.
    auto remark =
        RemarkMissed("memory", *rvi,
                     SourceLocInferenceBehavior::ForwardScanAlwaysInfer)
        << "retain of type '" << NV("ValueType", rvi->getOperand()->getType())
        << "'";
    for (auto arg : inferredArgs) {
      remark << arg;
    }
    return remark;
  });
}

void OptRemarkGeneratorInstructionVisitor::visitReleaseValueInst(
    ReleaseValueInst *rvi) {
  ORE.emit([&]() {
    using namespace OptRemark;
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs = valueToDeclInferrer.infer(ArgumentKeyKind::Note,
                                               rvi->getOperand(), inferredArgs);
    (void)foundArgs;

    // Releases end a lifetime scope so we infer scan backward.
    auto remark =
        RemarkMissed("memory", *rvi,
                     SourceLocInferenceBehavior::BackwardScanAlwaysInfer)
        << "release of type '" << NV("ValueType", rvi->getOperand()->getType())
        << "'";
    for (auto arg : inferredArgs) {
      remark << arg;
    }
    return remark;
  });
}

void OptRemarkGeneratorInstructionVisitor::visitAllocRefInst(
    AllocRefInst *ari) {
  if (ari->canAllocOnStack()) {
    return ORE.emit([&]() {
      using namespace OptRemark;
      SmallVector<Argument, 8> inferredArgs;
      bool foundArgs =
          valueToDeclInferrer.infer(ArgumentKeyKind::Note, ari, inferredArgs);
      (void)foundArgs;
      auto resultRemark =
          RemarkPassed("memory", *ari, SourceLocInferenceBehavior::ForwardScan)
          << "stack allocated ref of type '" << NV("ValueType", ari->getType())
          << "'";
      for (auto &arg : inferredArgs)
        resultRemark << arg;
      return resultRemark;
    });
  }

  return ORE.emit([&]() {
    using namespace OptRemark;
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs =
        valueToDeclInferrer.infer(ArgumentKeyKind::Note, ari, inferredArgs);
    (void)foundArgs;

    auto resultRemark =
        RemarkMissed("memory", *ari, SourceLocInferenceBehavior::ForwardScan)
        << "heap allocated ref of type '" << NV("ValueType", ari->getType())
        << "'";
    for (auto &arg : inferredArgs)
      resultRemark << arg;
    return resultRemark;
  });
}

void OptRemarkGeneratorInstructionVisitor::visitAllocBoxInst(
    AllocBoxInst *abi) {
  return ORE.emit([&]() {
    using namespace OptRemark;
    SmallVector<Argument, 8> inferredArgs;
    bool foundArgs =
        valueToDeclInferrer.infer(ArgumentKeyKind::Note, abi, inferredArgs);
    (void)foundArgs;

    auto resultRemark =
        RemarkMissed("memory", *abi, SourceLocInferenceBehavior::ForwardScan)
        << "heap allocated box of type '" << NV("ValueType", abi->getType())
        << "'";
    for (auto &arg : inferredArgs)
      resultRemark << arg;
    return resultRemark;
  });
}

//===----------------------------------------------------------------------===//
//                            Top Level Entrypoint
//===----------------------------------------------------------------------===//

namespace {

class OptRemarkGenerator : public SILFunctionTransform {
  ~OptRemarkGenerator() override {}

  bool isOptRemarksEnabled() {
    auto *fn = getFunction();
    // TODO: Put this on LangOpts as a helper.
    auto &langOpts = fn->getASTContext().LangOpts;

    return bool(langOpts.OptimizationRemarkMissedPattern) ||
           bool(langOpts.OptimizationRemarkPassedPattern) ||
           fn->getModule().getSILRemarkStreamer() ||
           fn->hasSemanticsAttrThatStartsWith(
               semantics::FORCE_EMIT_OPT_REMARK_PREFIX);
  }

  /// The entry point to the transformation.
  void run() override {
    if (!isOptRemarksEnabled())
      return;

    auto *fn = getFunction();

    // Skip top level implicit functions and top level autogenerated functions,
    // unless we were asked by the user to emit them.
    if (!ForceVisitImplicitAutogeneratedFunctions) {
      // Skip implicit functions generated by Sema.
      if (auto *ctx = fn->getDeclContext())
        if (auto *decl = ctx->getAsDecl())
          if (decl->isImplicit())
            return;
      // Skip autogenerated functions generated by SILGen.
      if (auto loc = fn->getDebugScope()->getLoc())
        if (loc.isAutoGenerated())
          return;
    }

    LLVM_DEBUG(llvm::dbgs() << "Visiting: " << fn->getName() << "\n");
    auto &rcfi = *getAnalysis<RCIdentityAnalysis>()->get(fn);
    OptRemarkGeneratorInstructionVisitor visitor(*fn, rcfi);
    for (auto &block : *fn) {
      for (auto &inst : block) {
        visitor.visit(&inst);
      }
    }
  }
};

} // end anonymous namespace

SILTransform *swift::createOptRemarkGenerator() {
  return new OptRemarkGenerator();
}
